1. Field of the Invention
The present invention relates generally to a communication system using a Low-Density Parity-Check (LDPC) code, and more particularly, to an apparatus and a method, which efficiently generate an LDPC code and implement encoding and decoding of a channel.
2. Description of the Related Art
Inter-Symbol Interference (ISI) as well as various noises and fading of a channel significantly reduce the performance of a link in a wireless communication system. Therefore, it is essential to develop technology for overcoming the noise, fading, and ISI for the purpose of implementing high-speed digital communication systems, which require a large amount of data processing, high-speed data processing, and high reliability of data, such as next generation mobile communication, digital broadcasting, and mobile Internet. Active research has recently been conducted for utilization of an error-correcting code as a method for efficiently restoring the distorted information to its original state and improving the reliability of communication.
The LDPC code, which was first introduced by Gallager in the 1960's, has been underutilized due to its complex implementation, which by far surpassed the technology at that time. However, because a turbo code discovered by Berrou, Glavieux, and Thitimajshima in 1993 shows performance approaching Shannon's channel capacity, much analytical research has been conducted on the performance and characteristics of the turbo code. With this, much research has been conducted on channel encoding based on iterative decoding and graphs.
The research as described above has led to restudies of the LDPC code in the late 1990's. The restudies showed that the performance of the LDPC code approaches the Shannon's channel capacity when decoding is performed using the iterative decoding based on a sum-product algorithm on a Tanner graph (a special case of a factor graph) corresponding to the LDPC code.
The LDPC code is usually represented using a graph representation method. Also, many characteristics of the LDPC code can be analyzed using methods based on graph theory, algebra, and probability theory. In general, a graph model of a channel code is useful for describing a code. When information on an encoded bit corresponds to a vertex in a graph and the relation between encoded bits corresponds to an edge (i.e. a line segment) in the graph, the graph model of the channel code may be considered a communication network in which vertexes exchange predetermined messages through edges. Accordingly, it is possible to derive a natural decoding algorithm. For example, a decoding algorithm derived from a trellis, which may be considered a type of graph, includes a well-known Viterbi algorithm and a Bahl, Cocke, Jelinek, and Raviv (BCJR) algorithm.
The LDPC code is usually defined by a parity-check matrix, and can be represented using a bipartite graph commonly called a Tanner graph. In the bipartite graph, vertexes are divided into two different types. The LDPC code is represented by the bipartite graph formed by vertexes called “variable node” and “check node.” A variable node corresponds to an encoded bit in the ratio of one to one.
Referring to FIGS. 1 and 2, a description is provided of a graph representation method of the LDPC code.
First, FIG. 1 illustrates an example of a parity-check matrix H1 of the LDPC code, which includes four rows and eight columns. Referring to FIG. 1, 8 columns signify an LDPC code, which generates a codeword with a length of 8, and each column corresponds to encoded 8 bits.
FIG. 2 is a diagram illustrating a Tanner graph corresponding to H1 of FIG. 1.
Referring to FIG. 2, the Tanner graph of the LDPC code includes eight variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214 and x8 216, and 4 check nodes 218, 220, 222 and 224.
Herein, the ith column and jth row in the parity-check matrix H1 of the LDPC code correspond to the variable node xi and the jth check node, respectively. Also, the value 1, namely, which is not zero, of a position where the ith column intersects the jth row in the parity-check matrix H1 of the LDPC code, implies that an edge exists between the variable node xi and the jth check node in the Tanner graph of FIG. 2.
The degrees of each variable node and each check node in the Tanner graph of the LDPC code signify the number of edges making a connection between the nodes. The number of edges is equal to the number of entries (i.e. elements), which are not zeros, in a column or row corresponding to a relevant node in the parity-check matrix H1 of the LDPC code.
For example, in FIG. 2, the degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214 and x8 216 are 4, 3, 3, 3, 2, 2, 2 and 2, respectively. The degrees of the check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5, respectively. Also, the numbers of entries, which are not zeros, in columns of the parity-check matrix H1 of FIG. 1 respectively corresponding to the variable nodes of FIG. 2 coincide with degrees 4, 3, 3, 3, 2, 2, 2 and 2, in regular sequence. The numbers of entries, which are not zeros, in rows of the parity-check matrix H1 of FIG. 1 respectively corresponding to the check nodes of FIG. 2 coincide with degrees 6, 5, 5 and 5, in regular sequence.
In order to represent the degree distribution of the nodes of the LDPC code, the ratio of the number of variable nodes, all having a degree of I, to the total number of variable nodes, is set to fi, and the ratio of the number of check nodes, all having a degree of j, to the total number of check nodes, is set to gj.
For example, in the case of the LDPC code as shown in FIGS. 1 and 2, fi=0 with respect to f2= 4/8, f3=⅜, f4=⅛, and i≠2, 3, and 4, and gj=0 with respect to g5=¾, g6=¼, and j≠5 and 6. When the length of the LDPC code is set to N (i.e. the number of columns is set to N) and the number of rows is set to N/2, a density of entries, which are not zeros, in the entire parity-check matrix having the degree distribution as described above is calculated by Equation (1) below.
                                                        2              ⁢                              f                2                            ⁢              N                        +                          3              ⁢                              f                3                            ⁢              N                        +                          4              ⁢                              f                4                            ⁢              N                                            N            ×                          N              /              2                                      =                  5.25          N                                    (        1        )            
In Equation (1), the density of is continues to decrease in the parity-check matrix H1 when N increases. It is usual that the density of entries, which are not zeros, is inversely proportional to the code length N in the LDPC code. Accordingly, when N is large, the density of the entries, which are not zeros, is very small. For this reason, the LDPC code includes the meaning of low-density in its name.
Structural characteristics of the parity-check matrix H1 of the LDPC code, to which the present invention is applied, are described with reference to FIG. 3.
FIG. 3 illustrates the LDPC code adopted as a standard technology in Digital Video Broadcasting-Satellite transmission 2nd generation (DVB-S2), one of the digital broadcasting standards.
In FIG. 3, N1 and K1 represent a block length and length of an information word in the LDPC code. (N1−K1) represents parity length. Also, M1 and q are determined in such a manner that q=(N1−K1)/M1 may be established. At this time, K1/M1 is determined to be an integer.
Referring to FIG. 3, the structure of a parity part (i.e. from the K1th column to the (N1−1)th column) in the parity-check matrix is in a dual diagonal form. Accordingly, degree distributions of columns, which correspond to the parity part, all have a value of 2, except for the last column all having a value of 1.
Rules applied to the structure of the information word part (i.e. from the 0th column to the (K1−1)th column) in the parity-check matrix are as follows.
Rule 1: K1/M1 column groups are generated in total by dividing K1 columns corresponding to the information word in the parity-check matrix into groups, each of which has M1 columns.
A method for forming a column belonging to each column group follows Rule 2 below.
Rule 2: positions of 1 s are determined in the 0th column of the ith (i=1, . . . , K1/M1) column group.
When the degree of the 0th column belonging to the ith column group is represented as Di, if it is assumed that positions of rows having is as their entries are represented as Ri,0(1), Ri,0(2), . . . Ri,0(Di), positions Ri,j(k)(k=1, 2, . . . , Di) of the rows, which have is as their entries in the jth (j=1, 2, . . . , M1−1) column belonging to the ith column group, are defined by Equation (2) below.Ri,j(k)=Ri,(j−1)(k)+q mod(N1−K1)k=1, 2, . . . , Di, i=1, . . . , K1/M1, and j=1, . . . , M1−1   (2)
When Rule 2 is applied, degrees of the columns belonging to the ith (i=1, . . . , K1/M1) column group are all fixed to Di. In order to facilitate easy understanding of the structure of the DVB-S2 LDPC code, which stores therein information on the parity-check matrix by Rule 2, the following example is considered.
When it is assumed that N1=30, K1=15, M1=5, and q=3, position information of rows having 1 s as their entries in each of the 0th columns of three column groups can be expressed as three sequences below. Herein, for the convenience of description, the three sequences are defined by weight-1 position sequences below.R1,0(1)=0, R1,0(2)=1, R1,0(3)=2,R2,0(1)=0, R2,0(2)=11, R2,0(3)=13,R3,0(1)=0, R3,0(2)=10, R3,0(3)=14
The weight-1 position sequences may be expressed as only relevant position information for each column group as follows:
0 1 2
0 11 13
0 10 14.
Namely, a sequence of the ith column is obtained by sequentially representing the position information of the rows having 1 s as their entries in the ith column group.
When a parity-check matrix is formed using both information corresponding to the example and Rules 1 and 2 as described above, an LDPC code of FIG. 4 below can be generated in such a manner as to have the same conception as that of the DVB-S2 LDPC code.
FIG. 4 illustrates an example of the parity-check matrix of the LDPC code.
It is possible to perform efficient encoding using a structural form in the DVB-S2 LDPC code designed by Rules 1 and 2. A process for performing LDPC encoding using the parity-check matrix of the DVB-S2 is described using the following example.
An encoding process using the DVB-S2 LDPC code when N1=16200, K1=10800, M1=360 and q=15, is provided. Also, information word bits with a length of K1 are represented as (i0, i1, . . . , iK1−1), and parity bits with a length of (N1−K1) are represented as (p0, p1, . . . , pN1−K1−1).
Step 1: an encoder initializes parity bits as follows:p0=p1= . . . =pN1−K1−1=0.
Step 2: information on rows, which have 1 s as their entries in the 0th column belonging to the first column group of an information word, is read from position information of the stored parity-check matrix.
An example of only relevant position information of the read information can be represented as follows:
0 2084 1613 1548 1286 1460 3196 4297 2481 3369 3451 46202622.
Also, multiple pieces of the relevant position information of the read information can be expressed as weight-1 position sequences as follows:R1,0(1)=0, R1,0(2)=2084, R1,0(3)=1613, R1,0(4)=1548, R1,0(5)=1286,R1,0(6)=1460, R1,0(7)=3196, R1,0(8)=4297, R1,0(9)=2481, R1,0(10)=3369,R1,0(11)=3451, R1,0(12)=4620 , R1,0(12)=2622.
The read information and an information bit i0 are used to update particular parity bits pxs, as defined in Equation (3) below, where x represents each of R1,0(k), k+1, 2, . . . , and 13.p0=p0⊕i0, p2084=p2084⊕i0, p1613=p1613⊕i0,p1548=p1548⊕i0, p1286=p1286⊕i0, p1460=p1460⊕i0,p3196=p3196⊕i0, p4297=p4297⊕i0, p2481=p2481⊕i0,p3369=p3369⊕i0, p3451=p3451⊕i0, p4620=p4620⊕i0,p2622=p2622⊕i0   (3)
In Equation (3), px=px⊕i0 may be represented as px←px⊕i0, and ⊕ signifies a binary addition.
Step 3: the value of each of 359 information word bits im (m=1, 2, . . . , 359) following i0 is calculated by Equation (4) below.{x+(m mod M1)×q}mod(N1−K1), M1=360, and m=1, 2, . . . , 359   (4)
In Equation (4), x represents the value of each of R1,0(k), k+1, 2, . . . , 13. In this case, equation (4) has the same concept as equation (2).
Next, the values obtained by equation (4) are used to perform calculations similar to Equation (3).
Namely, P{x+(m mod M1)×q}mod(N1−K1) is updated for im. For example, when m=1, i.e. for i1, P(x+q) mod(N1−K1) are updated by Equation (5) below.p15=p15⊕i1, p2099=p2099⊕i1, p1628=p1628⊕i1 p1563=p1563⊕i1, p1301=p1301⊕i1, p1475=p1475⊕i1,p3211=p3211⊕i1, p4312=p4312⊕i1, p2496=p2496⊕i1,p3384=p3384⊕i1, p3466=p3466⊕i1, p4635=p4635⊕i1,p2637=p2637⊕i1   (5)
Equation (5) corresponds to a case where q is assumed to be equal to 15. The process as described above is performed in the same manner for m=1, 2, . . . , 359.
Step 4: information of R2,0(k) (k=1, 2, . . . , 13) is read and a particular parity bit px is updated, with respect to the 361st information word bit i360 in the same manner as Step 2 as described above. Herein, x represents R2,0(k). P{x+(m mod M1)×q}mod(N1−K1) (where m=361, 362, . . . , 719) is updated by similarly applying Equation (4) to 359 information word bits i361, i362, . . . and i719 following i360.
Step 5: the process of Steps 2, 3 and 4 is repeated for each information word bit group with 360 information word bits.
Step 6: finally, parity bits are determined by Equation (6) below.pi=pi⊕pi−1(i=1, 2, . . . , N1−K1−1)   (6)
In Equation (6), pis are parity bits obtained by completing the LDPC encoding.
The LDPC encoding is performed through the process of Steps 1 to 6 in the DVB-S2, as described above.
Meanwhile, the LDPC encoding as described above should be designed in a manner suitable for supporting the amount of data transmission required by an actual communication system. Particularly, LDPC encoding having various block lengths for supporting various amounts of data transmission according to service requests is necessary for a communication system supporting various broadcasting services, as well as an adaptive communication system, to which a Hybrid Automatic Retransmission reQuest (HARM) scheme, an Adaptive
Modulation and Coding (AMC) scheme, etc. are applied for supporting high-speed data transmission.
However, in the conventional LDPC encoding, LDPC codewords all having the same length are generated, so that there is a limit on encoding and decoding a channel.
Therefore, an LDPC encoding scheme is necessary for a high-speed digital communication system, which requires a larger amount of data processing, higher-speed data processing, and higher reliability of data. Also, there is a need for channel encoding and decoding schemes, to which a more efficient LDPC codeword is applied.